package com.zhang.study.chapter03;


import java.util.Collection;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

import static com.zhang.util.RandomArrayUtil.generateRandomArray;

/**
 * 使用双链表实现队列
 */
public class Code04_DoubleNodeMyQueue {

    // 双链表节点结构
    public static class DoubleNode<T> {
        public T value;

        public DoubleNode<T> next;

        public DoubleNode<T> previous;

        public DoubleNode(T value) {
            this.value = value;
        }

        public DoubleNode() {
        }
    }

    /**
     * 使用双链表实现的队列 队列:先进先出
     * 队列需要实现的方法:
     * 1. 从头部插入
     * 2. 从尾部插入
     * 3. 从头部取
     * 4. 从尾部取
     */
    public static class MyQueueByDoubleNode<T> {
        public DoubleNode<T> begin;
        public DoubleNode<T> end;

        public MyQueueByDoubleNode() {
        }

        public MyQueueByDoubleNode(Collection<T> collection) {
            if (collection == null) {
                throw new NullPointerException("collection is null");
            }
            if (collection.isEmpty()) {
                throw new RuntimeException("collection is empty");
            }

            for (T t : collection) {
                DoubleNode<T> node = new DoubleNode<>(t);
                if (begin == null) {
                    begin = node;
                } else {
                    node.previous = end;
                    end.next = node;
                }
                end = node;
            }
        }

        /**
         * 从头部加入元素
         *
         * @param data 元素
         */
        public void addFromHead(T data) {
            DoubleNode<T> node = new DoubleNode<>(data);
            if (begin == null) {
                begin = node;
                end = node;
            } else {
                node.next = begin;
                begin.previous = node;
                begin = node;
            }
        }

        /**
         * 从尾部加入元素
         *
         * @param data 元素
         */
        public void addFromEnd(T data) {
            DoubleNode<T> node = new DoubleNode<>(data);
            if (begin == null) {
                begin = node;
            } else {
                end.next = node;
                node.previous = end;
            }
            end = node;
        }

        /**
         * 从头部移除元素
         *
         * @return 移除的元素
         */
        public T removeFromHead() {
            if (begin == null) {
                return null;
            }
            DoubleNode<T> cur = begin;
            if (begin == end) {
                begin = null;
                end = null;
            } else {
                begin = cur.next;
                cur.next = null;
                begin.previous = null;
            }
            return cur.value;
        }

        /**
         * 从尾部删除元素
         *
         * @return 删除元素
         */
        public T removeFromEnd() {
            if (end == null) {
                return null;
            }
            DoubleNode<T> cur = end;
            if (begin == end) {
                begin = null;
                end = null;
            } else {
                end = cur.previous;
                cur.previous = null;
                end.next = null;
            }
            return cur.value;
        }


    }

    public static void main(String[] args) {
        int len = 5000;
        int value = 10000;
        int testTime = 10000;

        System.out.println("test begin!");
        for (int i = 0; i < testTime; i++) {
            // 生成链表头结点
            int[] intArr = generateRandomArray(len, value);
            List<Integer> collect = IntStream.of(intArr).boxed().collect(Collectors.toList());
            MyQueueByDoubleNode<Integer> myQueueByDoubleNode = new MyQueueByDoubleNode<>(collect);
            LinkedList<Integer> linkedList = new LinkedList<>(collect);
            if (!testQueue(myQueueByDoubleNode, linkedList)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test finish!");

    }

    private static boolean testQueue(MyQueueByDoubleNode<Integer> myQueueByDoubleNode, LinkedList<Integer> linkedList) {
        int times = linkedList.size() - 1;
        while (times >= 0) {
            double random = Math.random();
            int i = (int) (Math.random() * 100 - Math.random() * 10);
            if (random >= 0.75) {
                // 从头部加一个元素
                myQueueByDoubleNode.addFromHead(i);
                linkedList.addFirst(i);
            } else if (random >= 0.5) {
                // 从尾部加一个元素
                myQueueByDoubleNode.addFromEnd(i);
                linkedList.addLast(i);
            } else if (random >= 0.25) {
                // 从头部删除一个元素
                Integer integer = myQueueByDoubleNode.removeFromHead();
                Integer integer1 = linkedList.removeFirst();
                if (testValid(integer, integer1)) return false;
            } else {
                // 从尾部删除一个元素
                Integer integer = myQueueByDoubleNode.removeFromEnd();
                Integer integer1 = linkedList.removeLast();
                if (testValid(integer, integer1)) return false;
            }
            times--;
        }
        while (!linkedList.isEmpty()) {
            Integer integer = myQueueByDoubleNode.removeFromHead();
            Integer first = linkedList.removeFirst();
            if (!integer.equals(first)) {
                return false;
            }
        }
        return true;
    }

    private static boolean testValid(Integer integer, Integer integer1) {
        if ((integer == null && integer1 != null) || (integer1 == null && integer != null)) {
            return true;
        }
        if (!(integer == null)) {
            return !integer.equals(integer1);
        }
        return false;
    }


}
